Magnum One

home *** CD-ROM | disk | FTP | other *** search

/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d3 / spellf.arc / SPELLF.DOC < prev

Wrap

Text File | 1989-10-30 | 18.7 KB | 404 lines

^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ DOCUMENTATION FOR ^ ^ ^ ^ SPELLF !Tiny Trainable Spellfilter Ver. 1.01 ^ ^ ^ ^ (c) 1989 Kas & Rita Thomas. All rights reserved. ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ You may distribute SPELLF to your friends. But if you do so, please register your copy with us today, by sending $10 (in cash, check, M.O., stamps, whatever) to: Kas & Rita Thomas, 578 Fairfield Ave., Stamford, CT 06902. This program was created using Borland Turbo C (Ver. 2.0). If you would like fully commented source code for SPELLF, kindly send $25 in lieu of the registration fee. In other words: For $25, you get source code AND registration, all in one shot (on disk). When you write, please tell us about your computer setup. Are you using SPELLF on a laptop? Which model? (Are you happy with it?) We'd be delighted to hear from you. Write to us today! WHAT IS SPELLF? AND: WHAT ISN'T IT? SPELLF is a spellfilter. We feel this word better describes the spirit of this utility than the term "spellchecker," which implies a literal brute-force comparison of words against a dictionary. SPELLF does not do this, obviously. (The "dictionary" file used by SPELLF is only 8K in size!) Rather than check literal spellings, SPELLF checks the "legality" of substrings within each word and reports out any words that contain illegal letter combinations. In this way, SPELLF acts more like a logical filter than a mere word-looker-upper. You give a text file to SPELLF, and the program acts as a sieve, reading the text file in and passing suspect words to "stdout" (the standard output device for your computer; usually the console). The output is fully redirectable, which means you can have it show up on your printer (or on disk) rather than on your screen. SPELLF carries out its filtering at lightning speed: On the slowest 8- MHz XT clone we could find, SPELLF took only 10 seconds to spellcheck a 120K text file! (It adds words to the main dictionary at the blistering rate of 1,000 English words -- about 6 Kbytes -- per second.) On a 286 or 386 machine, you may see throughput rates five to ten times higher. Especially if you use redirection. (The biggest runtime bottleneck for SPELLF is waiting for the screen to update.) Speed isn't SPELLF's primary virtue, however. Small size (both in terms of disk image and RAM overhead) is where SPELLF really shines. The program itself is just 12K, making it perfect for use on floppy- disk-only systems (laptops, for example) and systems that can't accommodate the 200K spellcheckers that come with such programs as ... well, you know the big names. At runtime, SPELLF uses approxi- mately 76K of RAM (12K of core RAM and 64K of "far core" heap space). For its dictionary, SPELLF uses a disk file only 8 kilobytes in size. No matter how many words you stuff into this dictionary file ($.DIC), it never gets bigger than precisely 8K. Another virtue of SPELLF is that it operates in command-line mode, making it easy to invoke spellchecking from batch files. And, SPELLF's output (a list of suspect words, with their line locations in the original file) is redirectable. That is, you can make the suspect-word list show up at your printer, or in a new file on disk, rather than on the screen. (Again, this approach lends itself to batch file applications.) DISCLAIMERS Whether or not you send us money, no warranties are made with respect to the program's performance, fitness, hardware compatibility, etc. To run this program, you need at least 72K of free RAM and 20K of disk space at all times. Any version of DOS should be fine. Note: This program is designed to spellcheck standard ASCII text files only. Nothing disastrous will happen if you attempt to spellcheck a WordStar file. SPELLF merely ignores high-bit characters. For this reason, control codes that fall outside the normal range of alpha-numeric ASCII characters pose no problem whatsoever. But if your word processor uses /b or /i for font calls, you may see erroneous exception-word callouts on the screen. If there is sufficient demand, we will rewrite the program to take care of format code detection. (Don't hold your breath, however!) THE $.DIC FILE Your program should have come bundled with an 8K file called $.DIC. SPELLF looks for this file at runtime; it contains the information needed to conduct spellchecking (or spellfiltering) operations. This file MUST be present in the current working directory, for SPELLF to work properly. The $.DIC dictionary file that we created for bundling with this program contains data for 20,000 commonly used English words. If you did not get a copy of $.DIC, don't panic: SPELLF will let you create your own $.DIC file, but you will have to supply your own core word list (of properly spelled words) with which to make the file. To create a brand-new $.DIC file from scratch, do this: 1. Be sure you are in a directory that contains no $.DIC file. (If a $.DIC file already exists, rename or delete it; otherwise the existing file will be UPDATED to contain the new word list.) 2. Run SPELLF with two arguments as follows: SPELLF {filename of word list} -a [Enter] Don't forget the "-a" on the command line. This tells SPELLF to ADD the contents of {filename} to $.DIC. If $.DIC did not exist before, a new file named $.DIC will show up in your current directory when you follow the above procedure. You will then be able to "spellcheck" any file against the $.DIC dictionary. If a $.DIC file already existed in the current directory, the contents (vocabulary) of {filename} will simply be ADDED to $.DIC. The previous contents of $.DIC will be preserved. It is a true ADD operation. CREATING CUSTOM DICTIONARIES Obviously, you can use the foregoing procedure to create any number of custom dictionaries (scientific word lists, lists of foreign words, computer terms, etc.) for use with the SPELLF program. All you need to do is supply the name of a file containing a list of scientific terms (or whatever) on the command line: SPELLF NEWWORDS.TXT -a [Enter] In this case, the vocabulary of NEWWORDS.TXT will be added to $.DIC. (Once again: If $.DIC did not already exist in the current working directory, it will be created. If it exists, it will be updated.) The filename does not have to have a .TXT extension; this is merely an example. Any extension is permissible. (Caution: If you accidentally supply the name of a spreadsheet or other non-text file, you stand a chance of corrupting your existing $.DIC file. Always keep a "good" copy of $.DIC on a backup disk somewhere.) Note that SPELLF is not merely an English-language spellchecker. If you happen to have a French word list on disk, you can use it to create a French-language version of $.DIC, and hence a French-language spellchecker. The copy of $.DIC that comes bundled with SPELLF happens to contain 20,000 English words. It could just as easily contain French, Spanish, German, or Italian words, etc. SPELLCHECKING To spellcheck a text file, just type SPELLF at the DOS prompt and supply the name of the text file you wish to examine. Then hit Enter. Example: SPELLF {filename} [Enter] If you type SPELLF DRAFT.DOC [Enter], the file DRAFT.DOC will be rigorously spell-checked using the words contained in $.DIC. (Remember that SPELLF expects the file $.DIC to be in the same directory as DRAFT.DOC.) A complete list of suspect words and their line locations will be printed to the screen. If you want, the list of suspect words can show up in a separate disk file, or be printed out on your printer. This is called redirection. To redirect the output of SPELLF to a brand-new file called BADWORDS, simply type: SPELLF DRAFT.DOC > BADWORDS [Enter] During program execution, in this case, nothing will happen on the screen (but the disk will be active). When the DOS prompt returns, you should see that there is a new file, BADWORDS, in your current directory. You can look at this file with the DOS command TYPE, or use your favorite word processor to open it. Note that SPELLF operates much faster when redirection to a file is used. That's because the process of displaying output on the screen (in SPELLF's default mode) is inherently slow -- slower, at least, than SPELLF's file I/O operations. You may wish, occasionally, to redirect output to your printer. Again, you can use DOS to do this: SPELLF DRAFT.DOC > PRN [Enter] This causes the file DRAFT.DOC to be spellchecked and the suspect words to appear at the printer, rather than at the screen. TESTING WORDS FOR PRESENCE IN THE DICTIONARY You can test words for presence or absence in the dictionary. The procedure is very simple: Just type SPELLF and -t. Like this: SPELLF -t [Enter] As soon as the program loads, a query message comes up on the screen asking you to supply a word. Just type it on the screen; then hit Enter. SPELLF will consult $.DIC to see if the word you typed is already in the dictionary. If it is, you'll be told so, and you will be asked if you want to test another word. (Type 'y' or Enter to answer in the affirmative.) If the word you typed was NOT in the dictionary, you'll be told so, and you will be given a chance to add it. No extra typing is required to add the word: Just hit Enter OR type 'y' for yes. (You must type 'n' if you do NOT wish to add the word to $.DIC.) You may keep checking words in this fashion for as long as you like. The loop will stop when you answer 'n' (No) to the "Test another word?" prompt. "Test" mode thus offers a second way (besides "Add" mode; see "CREATING CUSTOM DICTIONARIES," above) to update the dictionary. You can update the $.DIC dictionary one word at a time simply by entering the test-word loop as above, quitting at any convenient point. Obviously, when you have more than a handful of words to add to the dictionary, it makes sense to create a text file containing just the words in question, and "feed" it to SPELLF in "Add" mode by typing SPELLF <list name> -a , then Enter. SPELLCHECKING VS. SPELLFILTERING Conceptually, there are two ways to attack the problem of spellchecking: You can approach it in a brute-force manner, comparing every word in a file with entries in a dictionary . . . or you can approach it as an "expert system" type of problem, wherein an attempt is made to catalog all known rules of spelling (and spellcheck on a logical basis rather than a lookup basis). The first approach -- brute force lookup of words in an all-encompassing dictionary -- is familiar to anyone who has ever used a fully featured word processor. This approach is, in theory, infallible, provided the dictionary is complete. In the real world, no dictionary is ever large enough to approach completeness, nor CAN a dictionary ever be foolproof, due to the changing nature of the language. Proper nouns are always a problem, and new coinages are always entering the language. Indeed, the inherent "inventivity" of English is one of its most endearing characteristics. But this very property dooms all orthodox spell- checkers to failure. The second approach -- that of examining the rules governing spelling, and constructing a spellchecker based on those rules -- happens to coincide with the approach taken by most hyphenation programs. Most hyphenators are state machines whose main operations consist of affix analysis and word-root parsing. The same approach can be extended to spellchecking. Why not simply examine patterns of letters, and ask whether the individual patterns are "legal constructs" or "illegal constructs" based on known rules of English spelling? (Here, by patterns we mean more than just two-letter combinations.) An adaptation of this approach is used in SPELLF. The state-machine approach has many advantages over the brute-force method. For one thing, it requires no bulky dictionary (which, in many conventional programs, consumes 200K or more of disk space IN COMPACTED FORM). For another thing, it means that, in theory anyway, English words that don't exist yet can be spellchecked properly, because new coinages will always (presumably) follow the rules of English-language letter-combining. (That is, it's unlikely anybody will coin words that contain unpronounceable combinations like "xbjt" or "tqtpp.") A rule-based program should be able to spellcheck new coinages that it has not seen before. This is a formidable advantage over conventional spellchecking systems. SPELLF incorporates these ideas. Plus, it does so in ways that are simple, effective, and conducive to rapid program execution. When we say that SPELLF is a spellfilter, we mean simply that the goal of the program is to filter out illogical spellings and yield up a list of words whose letter-combinations don't make sense from the standpoint of known rules of English spelling. HOW THE PROGRAM WORKS (A TECHNICAL ASIDE, FOR PROGRAMMERS ONLY) If you're wondering how 20,000 or more English words can fit into an 8,192-byte dictionary file, consider that in 8,192 bytes there are 65,536 bits, each of which can represent a unique hash code. The $.DIC file that we've been discussing so far is not really a dictionary file in the true sense of the word, but a hash table, each one-bit entry of which represents a 16-bit hash code derived from a four-byte substring of whatever word is currently being examined. Words less than five letters long correspond to single entries in the hash table; words with five or more letters are carried in the table as multiple hashes. A five-letter word has two hash entries; a six-letter word has three hash entries; etc. During runtime, every word in a file is "factored out" into its constituent hash codes (however many there are), and each corresponding hash position in the $.DIC file is checked. If the hash check reveals a "legal" combination of four letters, the check succeeds; if the hash is illegal (representing a letter combination not found in the table), it fails and the word is flagged as "suspect." A 16-letter word such as "incomprehensible" contains 13 four-letter substrings and has 13 corresponding hash codes, each of which must be checked against entries in the $.DIC table. If even one check fails, the word is flagged as suspect, and printed to "stdout." The word "incomprehensible" must pass all 13 checks in order to be presumed correctly spelled. Notice that all checks are done in RAM; the disk is not accessed 13 times when "incomprehensible" is checked against $.DIC, because $.DIC is captured to RAM at runtime. The concept of hashing spellcheckers is not new; McIlroy created one for the PDP-11 (IEEE Trans. Comm. COM-30, Jan. 1982, pp. 91-99), and another attempt at such a program is discussed in CRAFTING TURBO C SOFTWARE COMPONENTS & UTILITIES by Richard S. Wiener (1988, Wiley & Sons). What is new about SPELLF is the small size of the hash table, and the concept of "spellfiltering" as opposed to conventional spellchecking from within a text document. No one talks about these programs as filters. But that's essentially what they are. You run SPELLF on a file in order to filter out bad words -- "suspect" words. The spelling is never actually "checked" in the literal sense. One can argue as to whether a 16-bit hash is adequate for a four- letter substring. We start from the assumption (which is demonstrably true) that five bits of information will suffice to encode 26 letters of the alphabet. We also know that 16 letters can be mapped precisely into four bits. Something slightly more than four bits is needed to unambiguously encode 26 letters, but the process of mapping 26 letters into four bits isn't as dangerous as it sounds, because: (1) the 16 most-frequently-used letters of the alphabet are used with very high frequency indeed, and (2) the remaining 10 letters can be assigned hash positions that tend to map over known-good portions of the hash table. Accordingly, in SPELLF, the ASCII table is renumbered to reflect frequency of usage and best-fit mapping, so that hash collisions are seldom "fatal" in the sense of allowing a wrong spelling to score as "right." Still, SPELLF is not perfect. There are times when a misspelled word is counted as correct. But this happens very infrequently. (If you want to get a feel for this, run the program in "test" mode and try to trick the dictionary with various misspellings of common words.) Please understand that we make no guarantee of SPELLF's spelling accuracy, nor do we contend that it is untrickable. SPELLF is imperfect -- like every spellchecker. What SPELLF lacks in precision, however, it more than makes up for in speed, ease of use, and compactness (to say nothing of its adaptability to batch file technique, redirectable output, etc.), and on balance, we feel the "filter" approach is every bit as useful in day-to-day usage as the orthodox big-dictionary brute-force approach. We'd love to know what YOU think; write to us at 578 Fairfield Ave., Stamford, CT 06902. And enclose $25 for full Turbo C source code, ready to compile in the tiny model. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *